package leetcode_贪心;

/**
 * @author yzh
 * @data 2021/3/29 21:22
 * 贪心算法
 * 局部最优：当前连续和为负数的时候立刻放弃，从下一个元素开始从新计算连续和
 * 因为负数加上下一个元素会使连续和越来越小
 */
public class _53_最大子序和 {
    public static void main(String[] args) {
        System.out.println(new _53_最大子序和().maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }

    public int maxSubArray(int[] nums) {
        int cur = 0, ans = Integer.MIN_VALUE;
        for (int num : nums) {
            cur += num;
            ans = Math.max(ans, cur);
            if (cur < 0) cur = 0;
        }
        return ans;
    }
}
